{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# K-Truss\n",
    "\n",
    "\n",
    "In this notebook, we will use cuGraph to identify the K-Truss clusters in a test graph  \n",
    "\n",
    "Notebook Credits\n",
    "* Original Authors: Bradley Rees\n",
    "* Created:   10/28/2019\n",
    "* Last Edit: 03/03/2020\n",
    "\n",
    "RAPIDS Versions: 0.13\n",
    "\n",
    "Test Hardware\n",
    "* GV100 32G, CUDA 10.2\n",
    "\n",
    "\n",
    "\n",
    "## Introduction\n",
    "\n",
    "Compute the k-truss of the graph G.  A K-Truss is a relaxed cliques where every vertex is supported by at least k-2 triangle.\n",
    "\n",
    "Ref:\n",
    "\n",
    "[1] Cohen, J.,\n",
    "    \"Trusses: Cohesive subgraphs for social network analysis\"\n",
    "    National security agency technical report, 2008\n",
    "\n",
    "[2] O. Green, J. Fox, E. Kim, F. Busato, et al.\n",
    "    “Quickly Finding a Truss in a Haystack”\n",
    "    IEEE High Performance Extreme Computing Conference (HPEC), 2017\n",
    "    https://doi.org/10.1109/HPEC.2017.8091038\n",
    "\n",
    "[3] O. Green, P. Yalamanchili, L.M. Munguia,\n",
    "    “Fast Triangle Counting on GPU”\n",
    "    Irregular Applications: Architectures and Algorithms (IA3), 2014\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To compute the K-Truss cluster in cuGraph use: <br>\n",
    "* __gc = cugraph.ktruss_subgraph(G,k=None, use_weights=True)__\n",
    "    G : cuGraph.Graph\n",
    "        cuGraph graph descriptor with connectivity information. k-Trusses are\n",
    "        defined for only undirected graphs as they are defined for\n",
    "        undirected triangle in a graph.\n",
    "\n",
    "    k : int\n",
    "        The desired k to be used for extracting the k-truss subgraph.\n",
    "\n",
    "    use_weights : Bool\n",
    "        whether the output should contain the edge weights if G has them\n",
    "    \n",
    "Returns:\n",
    "    G_truss : cuGraph.Graph\n",
    "        A cugraph graph descriptor with the k-truss subgraph for the given k.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## cuGraph Notice \n",
    "The current version of cuGraph has some limitations:\n",
    "\n",
    "* Vertex IDs need to be 32-bit integers.\n",
    "* Vertex IDs are expected to be contiguous integers starting from 0.\n",
    "\n",
    "cuGraph provides the renumber function to mitigate this problem. Input vertex IDs for the renumber function can be either 32-bit or 64-bit integers, can be non-contiguous, and can start from an arbitrary number. The renumber function maps the provided input vertex IDs to 32-bit contiguous integers starting from 0. cuGraph still requires the renumbered vertex IDs to be representable in 32-bit integers. These limitations are being addressed and will be fixed soon.    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Test Data\n",
    "We will be using the Zachary Karate club dataset \n",
    "*W. W. Zachary, An information flow model for conflict and fission in small groups, Journal of\n",
    "Anthropological Research 33, 452-473 (1977).*\n",
    "\n",
    "\n",
    "![Karate Club](../img/zachary_black_lines.png)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Prep"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Import needed libraries\n",
    "import cugraph\n",
    "import cudf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Read data using cuDF"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Test file    \n",
    "datafile='../data//karate-data.csv'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# read the data using cuDF\n",
    "gdf = cudf.read_csv(datafile, delimiter='\\t', names=['src', 'dst'], dtype=['int32', 'int32'] )"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# create a Graph \n",
    "G = cugraph.Graph()\n",
    "G.from_cudf_edgelist(gdf, source='src', destination='dst')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"Main Graph\")\n",
    "print(\"\\tNumber of Vertices: \" + str(G.number_of_vertices()))\n",
    "print(\"\\tNumber of Edges:    \" + str(G.number_of_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Now run K-Truss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call k-cores on the graph\n",
    "kcg = cugraph.ktruss_subgraph(G, 3) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"K-Truss Graph\")\n",
    "print(\"\\tNumber of Vertices: \" + str(kcg.number_of_vertices()))\n",
    "print(\"\\tNumber of Edges:    \" + str(kcg.number_of_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Let's looks at the results\n",
    "The results show that the roughly 2/3s of the edges have been removed.  \n",
    "Let's look at the degrees of the vertices"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "d = kcg.degrees()\n",
    "d.sort_values(by='out_degree', ascending=False)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# We can also just get a list of all the remaining edges as COO\n",
    "coo = kcg.view_edge_list()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# print out edge list\n",
    "coo"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Just for fun\n",
    "Let's try specifying a larger K value.  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Call k-cores on the graph\n",
    "kcg2 = cugraph.ktruss_subgraph(G, k=5) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "print(\"K-Truss Graph\")\n",
    "print(\"\\tNumber of Vertices: \" + str(kcg2.number_of_vertices()))\n",
    "print(\"\\tNumber of Edges:    \" + str(kcg2.number_of_edges()))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "Copyright (c) 2019-2020, NVIDIA CORPORATION.\n",
    "\n",
    "Licensed under the Apache License, Version 2.0 (the \"License\");  you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0\n",
    "\n",
    "Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.\n",
    "___"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "cugraph_dev",
   "language": "python",
   "name": "cugraph_dev"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
